| 翻訳と辞書 |
| upward planar drawing ： ウィキペディア英語版 |
upward planar drawing
In graph drawing, an upward planar drawing of a directed acyclic graph is an embedding of the graph into the Euclidean plane, in which the edges are represented as non-crossing monotonic upwards curves. That is, the curve representing each edge should have the property that every horizontal line intersects it in at most one point, and no two edges may intersect except at a shared endpoint.〔; .〕 In this sense, it is the ideal case for layered graph drawing, a style of graph drawing in which edges are monotonic curves that may cross, but in which crossings are to be minimized.
==Characterizations==
A directed acyclic graph must be planar in order to have an upward planar drawing, but not every planar acyclic graph has such a drawing. Among the planar directed acyclic graphs with a single source (vertex with no incoming edges) and sink (vertex with no outgoing edges), the graphs with upward planar drawings are the ''st''-planar graphs, planar graphs in which the source and sink both belong to the same face of at least one of the planar embeddings of the graph. More generally, a graph ''G'' has an upward planar drawing if and only if it is directed and acyclic, and is a subgraph of an ''st''-planar graph on the same vertex set.〔, pp. 111–112; , 6.1 "Inclusion in a Planar ''st''-Graph", pp. 172–179; ; .〕
In an upward embedding, the sets of incoming and outgoing edges incident to each vertex are contiguous in the cyclic ordering of the edges at the vertex. A planar embedding of a given directed acyclic graph is said to be ''bimodal'' when it has this property. Additionally, the angle between two consecutive edges with the same orientation at a given vertex may be labeled as ''small'' if it is less than π, or ''large'' if it is greater than π. Each source or sink must have exactly one large angle, and each vertex that is neither a source nor a sink must have none. Additionally, each internal face of the drawing must have two more small angles than large ones, and the external face must have two more large angles than small ones. A ''consistent assignment'' is a labeling of the angles that satisfies these properties; every upward embedding has a consistent assignment. Conversely, every directed acyclic graph that has a bimodal planar embedding with a consistent assignment has an upward planar drawing, that can be constructed from it in linear time.〔, pp. 112–115; , 6.2 "Angles in Upward Drawings", pp. 180–188; ; .〕
Another characterization is possible for graphs with a single source. In this case an upward planar embedding must have the source on the outer face, and every undirected cycle of the graph must have at least one vertex at which both cycle edges are incoming (for instance, the vertex with the highest placement in the drawing). Conversely, if an embedding has both of these properties, then it is equivalent to an upward embedding.〔, p. 115; , 6.7.2 "Forbidden Cycles for Single-Source Digraphs", pp. 209–210; .〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「upward planar drawing」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|